package dynamic;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

/**
 * 乘积最大子数组
 * 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 *
 * @author 罗俊华
 * @date 2022/1/5 - 10:50 上午
 */
@Slf4j
public class MaximumProductSubArray {

    private int[] ARR;

    public MaximumProductSubArray(int[] ARR) {
        this.ARR = ARR;
    }

    /**
     * 输入: [2,3,-2,4]
     * 输出: 6
     * 解释: 子数组 [2,3] 有最大乘积 6。
     *
     * @param args
     */
    public static void main(String[] args) {

//        MaximumProductSubArray m = new MaximumProductSubArray(new int[]{2, 3, -2, 4}); //6

//        MaximumProductSubArray m = new MaximumProductSubArray(new int[]{-2, 0, 1});  //0

//        MaximumProductSubArray m = new MaximumProductSubArray(new int[]{-2});   // -2
        MaximumProductSubArray m = new MaximumProductSubArray(new int[]{-3, -1, -1});  // 3

//        MaximumProductSubArray m = new MaximumProductSubArray(new int[]{-1, -2, -9, -6});  // 108

        int result = m.calculateMaxSubArray();

        log.info("最大乘积是：{}", result);

    }

    private int calculateMaxSubArray() {

        int[] maxCacheArray = new int[ARR.length];
        int[] minCacheArray = new int[ARR.length];

        int max = Integer.MIN_VALUE;

        for (int i = ARR.length - 1; i >= 0; i--) {
            max = Math.max(max, multiple(i, maxCacheArray, minCacheArray));
        }

        return max;
    }

    /**
     * 缺陷：只能算正数
     * @param startIndex
     * @param maxCacheArray
     * @param minCacheArray
     * @return
     */
    private int multiple(int startIndex, int[] maxCacheArray, int[] minCacheArray) {
        int max = ARR[startIndex];
        int min = ARR[startIndex];

        if (startIndex == ARR.length - 1) {
            maxCacheArray[ARR.length - 1] = max;
            minCacheArray[ARR.length - 1] = min;
            return max;//Math.max(max,min);
        }



        /*for (int i = startIndex + 1; i < ARR.length - 1; i++) {

            int maxCache = maxCacheArray[i];

            if (maxCache != Integer.MIN_VALUE) {

                max = Math.max(max, max * maxCache);

                break;
            }

//            一定能命中缓存，所以也就无需写没有命中的情况了
        }*/

//        缓存一定能命中
        int maxCache = maxCacheArray[startIndex + 1];
        int minCache = minCacheArray[startIndex + 1];

        max = Math.max(max, max * maxCache);
        min = Math.min(min, min * minCache);

//        更新缓存
        maxCacheArray[startIndex] = max;
        minCacheArray[startIndex] = min;
        /*if (ARR[startIndex] > 0) {
            return max;
        } else {
            return min;
        }*/
//        return Math.max(max, ARR[startIndex] * minCacheArray[startIndex + 1]);
        return max;
    }
}
